package com.wanxi.test;

import java.util.Arrays;

/**
 * 1.定义一个数组
 * 2.以第一个元素为基准数
 * 3.首先要得到索引 最左边的和左右边的索引，分别赋值left=0,right=arr.length-1;
 * 4.从右往左比较，比基准数小的，找到后得到索引：赋值给ri
 * 5.从左往右比较，比较基准数大的，找到索引，赋值给le；
 * 6.将这两个索引对应的数进行交换：前提条件（le<ri）
 * 7.  继续从4--6进行交换位置（递归）
 * 8.如果le==ri：那么就用基准数和le对应的数进行交换
 * 9.第一次循环结束，然后将这个数组以基准数分为左右两边的数组
 * 10.分别以左右两边的数组再次进行快速排序：执行4-8；（递归）
 */
public class FastSort {
    public static void main(String[] args) {
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int left = 0;
        int right = arr.length - 1;

        sort(arr, left, right);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(int[] arr, int left, int right) {
//        当左边的索引大于右边的索引，及退出递归
        if (left > right) {
            return;
        }
//        设定基准数
        int num = arr[left];
//        设定临时索引，即排序后的新左右索引，
        int le, ri;
////        最开始让临时索引和left，right相等
        le = left;
        ri = right;
        while (le < ri) {
//             注意，一定要先从右边往左边找，先确定右边的索引
//            从右边往左边比较，只要找到数小于基准数，则跳出，得到右边索引
            while (arr[ri] >= num && le < ri) {
                ri--;
            }
//            从左往右边比较，只要找到的数大于基准数，则跳出，得到左边的索引
//            且左边的一定小于右边的索引，不然就会进入死循环
            while (arr[le] <= num && le < ri) {
                le++;
            }
//            将刚刚的两个数进行交换
            if (le < ri) {
                int temp = arr[le];
                arr[le] = arr[ri];
                arr[ri] = temp;
            }

        }

//        将基准数和刚刚left和right相等时得到的数进行交换位置
        arr[left] = arr[le];
        arr[le] = num;
//        这里就以基准数开始，分为左右两个数组，分别对左右两边的数组做刚刚一样的排序即可
        sort(arr, left, le - 1);
        sort(arr, le + 1, right);
    }

}
